#include "graph.h"
using namespace std;

Graph::Graph(int V)
{
    //初始化点数
    this->V=V;
    //新建二维矩阵保存各点
    this->matrix=new int*[V];
    for(int i=0;i<V;i++)
    {
        matrix[i]=new int[V];
        //memset(matrix[i],0,sizeof(matrix[i]));
        for(int j=0;j<V;j++)
            matrix[i][j]=0;
    }
}

Graph::~Graph()
{
    for(int i=0;i<V;i++)
    {
        delete[] matrix[i];
    }
}

void
Graph::addEdge(int start,int end,int capacity)
{
    this->matrix[start][end]=capacity;
}

void
Graph::printMap()
{
    for(int i=0;i<V;i++)
    {
        for(int j=0;j<V;j++)
        {
            cout<<matrix[i][j]<<"\t";
        }
        cout<<endl;
    }
}

bool
Graph::dfs(int s,int t,vector<Edge> &path,bool * used)
{
    
    //cout<<s<<endl;
    if(used[s])             //如果已经到过了这条边
        return false;   //返回false
    
    used[s]=true;   //表示已经到过
    if(s==t)    //如果找到了
        return true;    //返回true  
    bool res=false;
    for(int i=0;i<V;i++)    
    {
        if(matrix[s][i]>0)  //遍历所有邻接顶点
        {
            res=dfs(i,t,path,used);   //递归搜素
            path.push_back(Edge(s,i,matrix[s][i]));   //推入边
            if(!res)    //如果此路不通
                path.pop_back(); //抛弃
            else    //否则
                return true;    //直接返回
        }
    }
    
    return res; //返回搜索结果
}

bool
Graph::find_path(int s,int t,vector<Edge> &path)
{
    bool * used;
    used=new bool[V];
    memset(used,false,sizeof(bool)*V);
    int res=dfs(s,t,path,used); //搜索并获取结果
    delete[] used;
    return res;
}

int
Graph::ford_fulkerson(int s,int t)
{
    int **f;
    f=new int*[V];
    for(int i=0;i<V;i++)    //设置所有f为0
    {
        f[i]=new int[V];
        for(int j=0;j<V;j++)
            f[i][j]=0;
    }
    vector<Edge> p; //增广路径
    while(find_path(s,t,p)) //当可以找到增广路径时
    {
        int cfp=INF;
        for(int i=0;i<p.size();i++)
        {
            if(cfp>p[i].capacity)
                cfp=p[i].capacity;  //找到最小的一条边的权值
        }
        for(int i=0;i<p.size();i++) //遍历每一条边
        {
            if(matrix[p[i].start][p[i].end]>0)  //如果在E中
            {
                f[p[i].start][p[i].end]+=cfp;   //流增加
                matrix[p[i].start][p[i].end]-=cfp;  //容量减少
            }
            else
            {
                f[p[i].start][p[i].end]-=cfp;   //流减少
                matrix[p[i].start][p[i].end]+=cfp;  //容量增加
            }
        }
        p.clear();  //清除记录
    }
    int sum=0;
    for(int i=0;i<V;i++)    //计算出边的流，即网络流
    {
        sum+=f[s][i];
    }
    for(int i=0;i<V;i++)
    {
        delete[] f[i];
    }
    return sum;
}

